package com.sicheng.lc.杂题.路径问题;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/18 22:03
 */
public class K站中转内最便宜的航班 {
    //https://leetcode.cn/problems/cheapest-flights-within-k-stops/
    static int INF = Integer.MAX_VALUE >> 2;
    static int N = 100;
    static int[] dist = new int[N];
    static int[] back = new int[N];

    // 基本原理是bellman-ford模板 有边数限制的最短路
    // 蓝桥杯图论目录下有这个板子
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Arrays.fill(dist, 0, n, INF);
        dist[src] = 0;
        for (int i = 0; i <= k; i++) {
            System.arraycopy(dist, 0, back, 0, n);
            for (int[] flight : flights) {
                int a = flight[0];
                int b = flight[1];
                int w = flight[2];
                dist[b] = Math.min(dist[b], back[a] + w);
            }
        }

        if (dist[dst] < INF >> 2)
            return dist[dst];
        return -1;
    }
}
